package main.leetcode.clockin.July;

/**
 * 32. 最长有效括号
 *
 * <p>给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
 *
 * <p>示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()"
 *
 * <p>示例 2: 输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"
 */
public class day4 {
    public static void main(String[] args) {
        System.out.println(new day4().longestValidParentheses(")()())"));
    }
    //  栈
    //    public int longestValidParentheses(String s) {
    //        if (s == null || s.length() == 0) {
    //            return 0;
    //        }
    //        Deque<Integer> stack = new LinkedList<>();
    //        stack.addLast(-1);
    //        int res = 0;
    //        for (int i = 0; i < s.length(); ++i) {
    //            if (s.charAt(i) == '(') {
    //                stack.addLast(i);
    //            } else {
    //                stack.pollLast();
    //                if (stack.isEmpty()) {
    //                    stack.addLast(i);
    //                } else {
    //                    res = Math.max(res, i - stack.peekLast());
    //                }
    //            }
    //        }
    //        return res;
    //    }

    // 动态规划
    public int longestValidParentheses(String s) {
        // 特判
        if (s == null || s.length() < 2) {
            return 0;
        }
        int n = s.length();
        // dp[i] 代表以i结尾的字符串的最长有效括号长度
        int[] dp = new int[n];
        int res = 0;
        // 可以直接从第1个开始
        for (int i = 1; i < n; ++i) {
            if (s.charAt(i) == ')') {
                // i - 1 是 '('，那就将以 i - 2 结尾的最长有效括号长度加上当前这个有效括号的长度
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i > 1 ? dp[i - 2] : 0) + 2;
                } else {
                    /*
                     preIndex 代表当前i号位的')'跳过前面这一长串有效括号后的位置，例如当前5号位，他所对应的preIndex就是2号位
                     如果这个位置是'('，那么就可以匹配上当前的')'
                     并且要考虑'('的前一个位置所对应的最长括号有效长度，前面可以通过'('和后面的连接在一起，
                     例如以1号位结尾的最长有效括号长度可以通过2号位的'('与以4号位结尾的最长有效括号长度连接在一起
                     “ 0 1 2 3 4 5 ”
                     “ ( ) ( ( ) ) ”
                     “ 0 2 0 0 2 4 ”
                    */
                    int preIndex = i - dp[i - 1] - 1;
                    if (preIndex >= 0 && s.charAt(preIndex) == '(') {
                        // 长度连接，注意边界判断
                        dp[i] = dp[i - 1] + (preIndex - 1 >= 0 ? dp[preIndex - 1] : 0) + 2;
                    }
                }
                // 更新
                res = Math.max(res, dp[i]);
            }
        }
        return res;
    }

    //    public int longestValidParentheses(String s) {
    //        // 特判
    //        if (s == null || s.length() < 2) {
    //            return 0;
    //        }
    //        int n = s.length();
    //        int res = 0;
    //        int left = 0, right = 0;
    //        // 从左到右
    //        for (int i = 0; i < n; ++i) {
    //            if (s.charAt(i) == '(') {
    //                ++left;
    //            } else {
    //                ++right;
    //            }
    //            if (left == right) {
    //                res = Math.max(res, left << 1);
    //            } else if (right > left) {
    //                left = right = 0;
    //            }
    //        }
    //        // 注意归零
    //        left = right = 0;
    //        // 从右到左
    //        for (int i = n - 1; i >= 0; --i) {
    //            if (s.charAt(i) == '(') {
    //                ++left;
    //            } else {
    //                ++right;
    //            }
    //            if (left == right) {
    //                res = Math.max(res, left << 1);
    //            } else if (left > right) {
    //                left = right = 0;
    //            }
    //        }
    //        return res;
    //    }
}
